package net.sf.nlp.ltag.parser.earley;

import java.util.ArrayList;
import java.util.List;
import java.util.Map;
import java.util.concurrent.ConcurrentLinkedQueue;
import org.apache.log4j.Logger;

import net.sf.nlp.ltag.data.LTAGNode;
import net.sf.nlp.ltag.data.LTAGTree;
import net.sf.nlp.ltag.data.LTAGTree.TreeType;
import net.sf.nlp.ltag.parser.LTAGState;
import net.sf.nlp.ltag.parser.ParserAlgAbstract;
import net.sf.nlp.ltag.parser.earley.EarleyState.POSITION;

public abstract class EarleyAlgAbstract extends ParserAlgAbstract
{
	protected static Logger logger =  Logger.getLogger(EarleyAlgAbstract.class);
	protected ConcurrentLinkedQueue<EarleyState> stateQueue;
	
	public EarleyAlgAbstract(Map<String, List<LTAGTree>> ltagMap)
	{
		super(ltagMap);
	}
	
	@Override
	public LTAGState generateLTAGState(LTAGTree tree, LTAGState state, int step)
	{
		EarleyState newState = new EarleyState(tree, step);
		
		if (state != null)
			newState.setFreq(state.getFreq());
		
		return newState;
	}
	
	public EarleyStateSet getInitEarleyStateSet() throws Exception
	{
		EarleyStateSet initStateSet = new EarleyStateSet(stateQueue);
		
		List<LTAGState> states = getInitStateSet();
		
		for (LTAGState state : states)
			initStateSet.addLTAGState((EarleyState)state);
		
		return initStateSet;
		
	}
	
	protected void calculateTask(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (scanner(stateSets, state, step))
			return;
		if (moveDotDown(stateSets, state, step))
			return;
		if (moveDotUp(stateSets, state, step))
			return;
	
		leftPredictor(stateSets, state, step);
		leftCompleter(stateSets, state, step);
		rightPredictor(stateSets, state, step);
		rightCompleter(stateSets, state, step);
		substitutionPredictor(stateSets, state, step);
		substitutionCompleter(stateSets, state, step);
	}

	public List<LTAGState> checkMatchedState(List<EarleyStateSet> stateSets)
	{
		if (stateSets.size() <= words.size())
			return null;
		
		EarleyStateSet matchedStateSet = stateSets.get(stateSets.size() - 1);
		
		List<LTAGState> matchedStates = new ArrayList<LTAGState>();
		
		for (EarleyState matchedState : matchedStateSet.getStates())
		{
			if (matchedState.getPos() != POSITION.RA || matchedState.getL() != 0 ||
				!matchedState.getNode().equals(matchedState.getTree().getRoot()))
				continue;
			
			if (matchedState.getFl() != -1 || matchedState.getFr() != -1)
				continue;
			
			if (matchedState.isMatched(words))
				matchedStates.add(matchedState);
		}
		
		return matchedStates;
	}
	
	private boolean scanner(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (step >= words.size())
			return false;
		
		if (state.getPos() != POSITION.LA)
			return false;
		
		LTAGNode node = state.getNode();
		
		if (!"#".equals(node.getType()))
			return false;
		
		//Word word = words.get((step + 1) - 1);
		//if (word.getLexical().equals(node.getWord().getLexical()))
		if (state.getTree().getWordIndex() == step)
		{
			EarleyState newState = (EarleyState)state.clone();
			newState.setId(stateCount.getAndIncrement());
			newState.setPreviousState(state);
			newState.setPos(POSITION.RA);
			newState.setStep(step + 1);
			
			synchronized(stateSets)
			{
				EarleyStateSet newStateSet = null;
				if ((step + 1) < stateSets.size())
					newStateSet = stateSets.get(step + 1);
				
				if (newStateSet == null)
				{
					newStateSet = new EarleyStateSet(stateQueue);
					stateSets.add(step + 1, newStateSet);
				}
				
				newStateSet.addLTAGState(newState);
			}
			return true;
		}
		
		return false;
	}
	
	private boolean moveDotDown(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.LB)
			return false;
		
		LTAGNode node = state.getNode();
		
		if (node.getChildren() == null || node.getChildren().size() == 0)
			return false;
		
		EarleyState newState = (EarleyState)state.clone();
		newState.setId(stateCount.getAndIncrement());
		newState.setPreviousState(state);
		newState.setStep(step);
		newState.setNode(node.getChildren().get(0));
		newState.setPos(POSITION.LA);
		stateSets.get(step).addLTAGState(newState);
		
		return true;
	}
	
	private boolean moveDotUp(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.RA)
			return false;
		
		LTAGNode node = state.getNode();
		
		if (state.getTree().getRoot().equals(node))
			return false;
		
		LTAGNode rb = node.getRightBrother();
		
		if (rb != null)
		{
			EarleyState newState = (EarleyState)state.clone();
			newState.setId(stateCount.getAndIncrement());
			newState.setPreviousState(state);
			newState.setStep(step);
			newState.setNode(rb);
			newState.setPos(POSITION.LA);
			stateSets.get(step).addLTAGState(newState);
		}
		else 
		{
			EarleyState newState = (EarleyState)state.clone();
			newState.setId(stateCount.getAndIncrement());
			newState.setPreviousState(state);
			newState.setStep(step);
			newState.setNode(node.getParent());
			newState.setPos(POSITION.RB);
			stateSets.get(step).addLTAGState(newState);
		}
		
		return true;
	}
	
	private boolean leftPredictor(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.LA)
			return false;
		
		LTAGNode node = state.getNode();
		
		boolean isMatched = false;
		///////////////////STEP 1////////////////////
		if (!"#".equals(node.getType()))
		{
			//if (!(state.getTree().getType() == TreeType.A && "*".equals(node.getType())))// &&
			//	!(state.getTree().getType() == TreeType.I && node.equals(state.getTree().getRoot())))
			if (!"*".equals(node.getType()) && !"$".equals(node.getType()))
			{
				List<LTAGState> adjunctStates = getAdjunctState(state, step);
				
				for (LTAGState newState : adjunctStates)
				{
					((EarleyState)newState).setL(step);
					stateSets.get(step).addLTAGState((EarleyState)newState);
					
					isMatched = true;
				}
			}
		}
		//////////////////////////////////////////////
		///////////////////STEP 2/////////////////////
		if ("*".equals(node.getType()))
		{
			if (state.getFl() == -1 && state.getFr() == -1)
			{
				EarleyState newState = (EarleyState)state.clone();
				newState.setId(stateCount.getAndIncrement());
				newState.setPreviousState(state);
				newState.setStep(step);
				newState.setPos(POSITION.LB);
				newState.setFl(step);
				newState.setFr(-1);
				stateSets.get(step).addLTAGState(newState);
				
				isMatched = true;
			}
		}
		else
		{
			EarleyState newState = (EarleyState)state.clone();
			newState.setId(stateCount.getAndIncrement());
			newState.setPreviousState(state);
			newState.setStep(step);
			newState.setPos(POSITION.LB);
			stateSets.get(step).addLTAGState(newState);
			
			isMatched = true;
		}
		
		return isMatched;
	}

	private boolean leftCompleter(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.LB || state.getFr() != -1)
			return false;
		if (TreeType.A != state.getTree().getType())
			return false;
		
		EarleyState parentState = (EarleyState)state.getParentState();
		if (parentState == null)
			return false;
		
		boolean matched = false;
		LTAGNode node = state.getNode();
		
		if (!"*".equals(node.getType()))
			return false;
		
		if (parentState.getPos() != POSITION.LA)
			return false;
		
		if (!parentState.getNode().getNodeText().equals(state.getTree().getRoot().getNodeText()))
			return false;
		
		int l = state.getL();

		if ("*".equals(parentState.getNode().getType()))
		{
			if (parentState.getFl() == -1 && parentState.getFr() == -1)
			{
				EarleyState newState = (EarleyState)parentState.simpleClone();
				newState.setId(stateCount.getAndIncrement());
				newState.setFreq(state.getFreq());
				newState.setPreviousState(state);
				newState.setStep(step);
				newState.setPos(POSITION.LB);
				newState.setFl(step);
				newState.setFr(-1);
				newState.setStar(newState.getNode());
				newState.setTl(l);
				newState.setBl(step);
				newState.setOperatorHistory(state.cloneOperatorHistory());
				newState.setParsedLeafNodes(state.cloneParsedLeafNodes());
				stateSets.get(step).addLTAGState(newState);
				
				matched = true;
			}
		}
		else
		{
			EarleyState newState = (EarleyState)parentState.simpleClone();
			newState.setId(stateCount.getAndIncrement());
			newState.setFreq(state.getFreq());
			newState.setPreviousState(state);
			newState.setStep(step);
			newState.setPos(POSITION.LB);
			newState.setStar(newState.getNode());
			newState.setTl(l);
			newState.setBl(step);
			newState.setOperatorHistory(state.cloneOperatorHistory());
			newState.setParsedLeafNodes(state.cloneParsedLeafNodes());
			stateSets.get(step).addLTAGState(newState);
			
			matched = true;
		}
		
		return matched;
	}
	
	private boolean rightPredictor(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.RB)
			return false;
		
		boolean matched = false;
		
		if (!state.getNode().equals(state.getStar()))
		{
			EarleyState newState = (EarleyState)state.clone();
			newState.setId(stateCount.getAndIncrement());
			newState.setPreviousState(state);
			newState.setStep(step);
			newState.setPos(POSITION.RA);
			stateSets.get(step).addLTAGState(newState);
				
			matched = true;
			
		}
		else
		{
			LTAGNode node = state.getNode();
			EarleyState previousState = state;
			EarleyState newState = null;
			EarleyState parentState;
			
			while ((previousState = (EarleyState)previousState.getPreviousState()) != null)
			{
				if (previousState.getStep() != state.getBl())
					continue;
				
				if (previousState.getPos() != POSITION.LB || previousState.getFr() != -1)
					continue;
				
				if (TreeType.A != previousState.getTree().getType())
					continue;
				
				if (!previousState.getNode().equals(previousState.getTree().getFoot()))
					continue;
				
				parentState = (EarleyState)previousState.getParentState();
				if (parentState == null)
					continue;
				
				if (!parentState.getNode().equals(node))
					continue;
				
				if (parentState.getPos() != POSITION.LA)
					continue;
				
				if (!previousState.getTree().getRoot().getNodeText().equals(node.getNodeText()))
					continue;
				
				newState = (EarleyState)previousState.simpleClone();
				newState.setId(stateCount.getAndIncrement());
				newState.setFreq(state.getFreq());
				newState.setPreviousState(state);
				newState.setStep(step);
				newState.setPos(POSITION.RB);
				newState.setFr(step);
				newState.setOperatorHistory(state.cloneOperatorHistory());
				newState.setParsedLeafNodes(state.cloneParsedLeafNodes());
				
				break;
			}
			
			if (newState != null)
			{
				stateSets.get(step).addLTAGState(newState);
				matched = true;
			}
		}
		
		return matched;
	}

	private boolean rightCompleter(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.RA)
			return false;
		
		if (TreeType.A != state.getTree().getType())
			return false;
		
		if (!state.getTree().getRoot().equals(state.getNode()))
			return false;
		
		if (!validateStatistic(state, bestResutCount))
			return false;
		
		boolean matched = false;
		int fr = state.getFr();
		
		if (fr == -1)
			return false;
		
		EarleyState parentState = (EarleyState)state.getParentState();
		
		if (parentState == null)
			return false;
		
		EarleyState newState = null;
		EarleyState previousState1 = state;
		EarleyState previousState2 = state;
		
		while ((previousState1 = (EarleyState)previousState1.getPreviousState()) != null)
		{
			if (previousState1.getStep() != state.getL())
				continue;
			
			if (!parentState.getNode().equals(previousState1.getNode()))
				continue;
			
			if (parentState.getPos() != POSITION.LA)
				continue;
			
			if (previousState1.getPos() != POSITION.LA)
				continue;
			
			while ((previousState2 = (EarleyState)previousState2.getPreviousState()) != null)
			{
				if (previousState2.getStep() !=state.getFr())
					continue;
				
				if (previousState2.getPos() != POSITION.RB || previousState1.getL() != previousState2.getL())
					continue;
				
				if (!previousState1.getTree().equals(previousState2.getTree()))
					continue;
				
				if (!previousState1.getNode().equals(previousState2.getNode()))
					continue;
				
				if (previousState1.getFl() != -1 && previousState1.getFl() != previousState2.getFl())
					continue;
				
				if (previousState1.getFr() != -1 && previousState1.getFr() != previousState2.getFr())
					continue;
				
				if (!previousState1.getNode().getNodeText().equals(state.getTree().getRoot().getNodeText()))
					continue;
				
				newState = (EarleyState)previousState1.simpleClone();
				newState.setId(stateCount.getAndIncrement());
				newState.setFreq(state.getFreq());
				newState.setPreviousState(state);
				newState.setStep(step);
				newState.setPos(POSITION.RA);
				newState.setFl(previousState2.getFl());
				newState.setFr(previousState2.getFr());
				newState.setOperatorHistory(state.cloneOperatorHistory());
				newState.setParsedLeafNodes(state.cloneParsedLeafNodes());
				
				break;
			}
			
			if (newState != null)
				break;
		}
		
		if (newState != null)
		{
			stateSets.get(step).addLTAGState(newState);
			matched = true;
		}
		
		
		return matched;
	}
	
	private boolean substitutionPredictor(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (step >= words.size())
			return false;
		
		if (state.getPos() != POSITION.LA)
			return false;
		
		LTAGNode node = state.getNode();
		
		if (!"$".equals(node.getType()))
			return false;
		
		List<LTAGState> substitutionStates = getSubstitutionState(state, step);
		
		for (LTAGState substitutionState : substitutionStates)
		{
			((EarleyState)substitutionState).setL(step);
			stateSets.get(step).addLTAGState((EarleyState)substitutionState);
		}
		
		return true;
	}
	
	private boolean substitutionCompleter(List<EarleyStateSet> stateSets, EarleyState state, int step)
	{
		if (state.getPos() != POSITION.RA || state.getFl() != -1 || state.getFr() != -1 || state.getStar() != null || state.getBl() != -1 || state.getTl() != -1)
			return false;
		
		if (TreeType.I != state.getTree().getType())
			return false;
		
		if (!state.getTree().getRoot().equals(state.getNode()))
			return false;
		
		if (!validateStatistic(state, bestResutCount))
			return false;
		
		EarleyState previousState = state;
		EarleyState parentState = (EarleyState)state.getParentState();
		boolean isMatched = false;
		
		while ((previousState = (EarleyState)previousState.getPreviousState()) != null)
		{
			if (previousState.getStep() != state.getL())
				continue;
			
			if (!previousState.equals(parentState))
				continue;
			
			if (previousState.getPos() != POSITION.LA)
				continue;
			
			if (!previousState.getNode().getNodeText().equals(state.getTree().getRoot().getNodeText()))
				continue;
			
			if (!"$".equals(previousState.getNode().getType()))
				continue;
			
			isMatched = true;
			break;
		}
			
		if (!isMatched)
			return false;
		
		EarleyState newState = (EarleyState)parentState.simpleClone();
		newState.setId(stateCount.getAndIncrement());
		newState.setFreq(state.getFreq());
		newState.setPreviousState(state);
		newState.setStep(step);
		newState.setPos(POSITION.RA);
		newState.setOperatorHistory(state.cloneOperatorHistory());
		newState.setParsedLeafNodes(state.cloneParsedLeafNodes());
		
		stateSets.get(step).addLTAGState(newState);
		
		return true;
	}
}
